package com.jxb.seven;

import java.util.Arrays;

/**
 * 不同路径
 *
 * 输入：m = 3, n = 7
 * 输出：28
 *
 * @author jiaobo
 * @date Created in 2025/1/5 14:16
 **/
public class UniquePaths_62 {


    //标准dp实现
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        //dp数组初始化
        for (int i = 0; i< m;++i) {
            dp[i][0]=1;
        }
        for (int j = 0;j<n;++j) {
            dp[0][j] = 1;
        }
        //使用状态转移公式，填充dp数组,空间O(m*n)
        for (int i = 1;i<m;++i) {
            for (int j = 1;j<n;++j) {
                //dp[2][4] = dp[1][4] + dp[2][3]
                dp[i][j] = dp[i-1][j] +dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

    //标准dp+滚动数组实现,空间:O(n)
    public int uniquePaths2(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        for (int i = 1;i<m;++i) {
            for (int j = 1;j<n;++j) {
                dp[j] = dp[j] + dp[j-1];
            }
        }
        return dp[n-1];
    }

}
